//快速排序优化
public class QuickSort2 {
    // 快速排序
    private static void swap(int[] array, int left, int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
    //Hare法
    private static int partitionHare(int[] array, int left, int right) {
        int i=left;
        int j=right;
        int provit=array[left];
        while(i<j){
            while(i<j && array[j]>=provit){
                j--;
            }
            while(i<j && array[i]<=provit){
                i++;
            }
            swap(array,i,j);
        }
        swap(array,left,i);
        return i;
    }
    //指针法
    private static int partition(int[] array, int left, int right) {
        int prev=left;
        int provit=array[left];
        int cur=prev+1;
        while(cur<=right){
            if(array[cur]<provit && array[prev]!=array[cur]){
                prev++;
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //挖坑法
    private static int partitionhole(int[] array, int left, int right) {
        int i=left;
        int j=right;
        int provit=array[left];
        while(i<j){
            while(i<j && array[j]>=provit){
                j--;
            }
            array[i]=array[j];
            while(i<j && array[i]<=provit){
                i++;
            }
            array[j]=array[i];
        }
        array[i]=provit;
        return i;
    }
    //递归左右子树
    public static int midindex(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[left] > array[mid]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else return mid;
        } else {
            if (array[right] > array[mid]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            }else return mid;
            }
        }
    public static void quickSort1(int[] array,int left,int right){
        if(left>=right) return;
        //三数取中 选取中间数作为基准
        int mid=midindex(array,left,right);
        swap(array,left,mid);
        int partition=partition(array,left,right);
        quickSort1(array,left,partition-1);
        quickSort1(array,partition+1,right);
    }
    public static void insertSort(int[] array,int left,int right){
        for(int i=left;i<=right;i++){
            int tmp=array[i];
            int j=i;
            while(j>0 && array[j-1]>tmp){
                array[j]=array[j-1];
                j--;
            }
            array[j]=tmp;
        }
    }
    public static void quickSort2(int[] array,int left,int right){
        if(left>=right) return;
        //当left与right接近时 ，直接使用插入排序
        if(right-left<7){
            insertSort(array,left,right);
            return;

        }
        int partition=partition(array,left,right);
        quickSort2(array,left,partition-1);
        quickSort2(array,partition+1,right);
    }
    public static void quickSort2(int[] array){
        quickSort2(array,0,array.length-1);
    }
    public static void quickSort1(int[] array){
        quickSort1(array,0,array.length-1);
    }
}
